package Example_practice02;

import java.util.Arrays;

class Item{
    public int weight;
    public int value;
    public Item(int weight,int value){
        this.weight=weight;
        this.value=value;
    }
}
public class Knapsack {
    //贪心算法实现0-1背包问题
    public static int getMaxValue(Item[] items,int capacity){
        //先排序，按照单位价值从大到小排序
        Arrays.sort(items,(it1,it2)->{
            double ratio1=it1.value/it1.weight;
            double ratio2=it2.value/it2.weight;
            if (ratio1<ratio2){
                return 1;
            } else if (ratio1>ratio2) {
                return -1;
            }else {
                return 0;
            }
        });

        int curCapacity=capacity;
        int totalValue=0;
        for (Item item:items){
            if (item.weight<=curCapacity){
                totalValue +=item.value;
                curCapacity-=item.weight;
            }
        }
        return totalValue;
    }
    //测试数据
    public static void main(String[] args){
        Item[] items={
                new Item(10,60),
                new Item(5,20),
                new Item(8,24),
                new Item(7,35),
                new Item(20,60),
        };
        int capacity=25;
        int maxValue=getMaxValue(items,capacity);
        System.out.println("背包包含的最大价值为："+maxValue);
    }
}
